package utils;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    public static TreeNode createTree(Integer... data) {
        // 使用队列存储.
        Deque<TreeNode> deque = new ArrayDeque<>();
        TreeNode treeNode = new TreeNode(data[0]);
        deque.offer(treeNode);
        int i = 1;
        while (!deque.isEmpty() && i < data.length) {
            TreeNode root = deque.pop();
            if (data[i] != null) {
                TreeNode left = new TreeNode(data[i]);
                deque.offer(left);
                root.left = left;
            }
            i++;
            if ( i < data.length && data[i] != null ) {
                TreeNode right = new TreeNode(data[i]);
                deque.offer(right);
                root.right = right;
            }
            i++;
        }
        return treeNode;
    }

    //二叉树的平序遍历
    public static List<Integer> printTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        ArrayList<Integer> result = new ArrayList<>();
        result.add(root.val);
        while (!deque.isEmpty()) {
            TreeNode pop = deque.pop();
            TreeNode left = pop.left;
            if(left!=null){
                deque.offer(left);
                result.add(left.val);
            }else {
                result.add(null);
            }
            TreeNode right = pop.right;
            if (right != null) {
                deque.offer(right);
                result.add(right.val);
            }else {
                result.add(null);
            }
        }
        int n =0;
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i)+" ");
            if (i == n) {
                n=2*(n+1);
                System.out.println();
            }
        }
        System.out.println();
        return result;
    }
}